The present disclosure relates generally to lock management, and more specifically to load management for locks on shared resources by embedding load management capabilities within the lock.
Concurrent algorithms (except those in the lock free class) utilize some sort of access control mechanism to ensure synchronization, that is, individual access to shared resources. Using mutual exclusion locks, for instance, each thread, before accessing an individual shared resource must acquire a lock, in order to continue, or, if the lock is not available, the thread waits until it has been released by the current owner.
In this context, thread waiting can be achieved in two possible ways. A busy lock may be used, that is, the thread enters a tight loop inspecting the lock, until it is found to be free. A passive lock may be used, in which the thread enqueues itself in a linked list of waiting threads and suspends execution, waiting to be woken up by the lock owner once the lock is available.
When more threads try to access the same lock than there are CPUs available, all the CPUs will end up being busy running tight loops trying to acquire the same lock. This causes a problem called “Starvation”. This will prevent other threads, whether they are trying to access the lock, or even worse, doing unrelated work, from acquiring CPU resources. Since all CPUs (bar the one associated with the lock owner) will be looping on the lock but not doing any useful work, the whole system will effectively be starved to a grinding halt. Some designs of busy locks become a bottleneck when a certain threshold load is applied to them. When this happens, the CPU spends more time getting past the locks than doing actual work, at the same time preventing threads that don't need the locks from doing any work.